/**
 * @file
 *
 * @author CCHyper
 * @author OmniBlade
 *
 * @brief Multiple precision arithmetic library for cryptographic functions.
 *
 * @copyright Chronoshift is free software: you can redistribute it and/or
 *            modify it under the terms of the GNU General Public License
 *            as published by the Free Software Foundation, either version
 *            2 of the License, or (at your option) any later version.
 *            A full copy of the GNU General Public License can be found in
 *            LICENSE
 */
#include "mpmath.h"
#include "endiantype.h"
#include "gamedebug.h"
#include "minmax.h"

#include <stdlib.h>

static mp_digit_u _scratch_modulus[MAX_UNIT_PRECISION];
static mp_digit_u _double_staging_number[MAX_UNIT_PRECISION * 2 + 2];
static mp_digit_u _upton_e_number[MAX_UNIT_PRECISION * 2 + 2];
static mp_digit_u _upton_f_number[MAX_UNIT_PRECISION * 2 + 2];
static mp_digit_u _upton_reciprocal[MAX_UNIT_PRECISION];
static mp_digit_u _upton_dhi[MAX_UNIT_PRECISION];
static int32_t _upton_bitsdiv;
static int32_t _upton_bitsmod;

static uint16_t mp_primeTable[MAX_PRIME_TABLE_SIZE] = {
    2,
    3,
    5,
    7,
    11,
    13,
    17,
    19,
    23,
    29,
    31,
    37,
    41,
    43,
    47,
    53,
    59,
    61,
    67,
    71,
    73,
    79,
    83,
    89,
    97,
    101,
    103,
    107,
    109,
    113,
    127,
    131,
    137,
    139,
    149,
    151,
    157,
    163,
    167,
    173,
    179,
    181,
    191,
    193,
    197,
    199,
    211,
    223,
    227,
    229,
    233,
    239,
    241,
    251,
    257,
    263,
    269,
    271,
    277,
    281,
    283,
    293,
    307,
    311,
    313,
    317,
    331,
    337,
    347,
    349,
    353,
    359,
    367,
    373,
    379,
    383,
    389,
    397,
    401,
    409,
    419,
    421,
    431,
    433,
    439,
    443,
    449,
    457,
    461,
    463,
    467,
    479,
    487,
    491,
    499,
    503,
    509,
    521,
    523,
    541,
    547,
    557,
    563,
    569,
    571,
    577,
    587,
    593,
    599,
    601,
    607,
    613,
    617,
    619,
    631,
    641,
    643,
    647,
    653,
    659,
    661,
    673,
    677,
    683,
    691,
    701,
    709,
    719,
    727,
    733,
    739,
    743,
    751,
    757,
    761,
    769,
    773,
    787,
    797,
    809,
    811,
    821,
    823,
    827,
    829,
    839,
    853,
    857,
    859,
    863,
    877,
    881,
    883,
    887,
    907,
    911,
    919,
    929,
    937,
    941,
    947,
    953,
    967,
    971,
    977,
    983,
    991,
    997,
    1009,
    1013,
    1019,
    1021,
    1031,
    1033,
    1039,
    1049,
    1051,
    1061,
    1063,
    1069,
    1087,
    1091,
    1093,
    1097,
    1103,
    1109,
    1117,
    1123,
    1129,
    1151,
    1153,
    1163,
    1171,
    1181,
    1187,
    1193,
    1201,
    1213,
    1217,
    1223,
    1229,
    1231,
    1237,
    1249,
    1259,
    1277,
    1279,
    1283,
    1289,
    1291,
    1297,
    1301,
    1303,
    1307,
    1319,
    1321,
    1327,
    1361,
    1367,
    1373,
    1381,
    1399,
    1409,
    1423,
    1427,
    1429,
    1433,
    1439,
    1447,
    1451,
    1453,
    1459,
    1471,
    1481,
    1483,
    1487,
    1489,
    1493,
    1499,
    1511,
    1523,
    1531,
    1543,
    1549,
    1553,
    1559,
    1567,
    1571,
    1579,
    1583,
    1597,
    1601,
    1607,
    1609,
    1613,
    1619,
    1621,
    1627,
    1637,
    1657,
    1663,
    1667,
    1669,
    1693,
    1697,
    1699,
    1709,
    1721,
    1723,
    1733,
    1741,
    1747,
    1753,
    1759,
    1777,
    1783,
    1787,
    1789,
    1801,
    1811,
    1823,
    1831,
    1847,
    1861,
    1867,
    1871,
    1873,
    1877,
    1879,
    1889,
    1901,
    1907,
    1913,
    1931,
    1933,
    1949,
    1951,
    1973,
    1979,
    1987,
    1993,
    1997,
    1999,
    2003,
    2011,
    2017,
    2027,
    2029,
    2039,
    2053,
    2063,
    2069,
    2081,
    2083,
    2087,
    2089,
    2099,
    2111,
    2113,
    2129,
    2131,
    2137,
    2141,
    2143,
    2153,
    2161,
    2179,
    2203,
    2207,
    2213,
    2221,
    2237,
    2239,
    2243,
    2251,
    2267,
    2269,
    2273,
    2281,
    2287,
    2293,
    2297,
    2309,
    2311,
    2333,
    2339,
    2341,
    2347,
    2351,
    2357,
    2371,
    2377,
    2381,
    2383,
    2389,
    2393,
    2399,
    2411,
    2417,
    2423,
    2437,
    2441,
    2447,
    2459,
    2467,
    2473,
    2477,
    2503,
    2521,
    2531,
    2539,
    2543,
    2549,
    2551,
    2557,
    2579,
    2591,
    2593,
    2609,
    2617,
    2621,
    2633,
    2647,
    2657,
    2659,
    2663,
    2671,
    2677,
    2683,
    2687,
    2689,
    2693,
    2699,
    2707,
    2711,
    2713,
    2719,
    2729,
    2731,
    2741,
    2749,
    2753,
    2767,
    2777,
    2789,
    2791,
    2797,
    2801,
    2803,
    2819,
    2833,
    2837,
    2843,
    2851,
    2857,
    2861,
    2879,
    2887,
    2897,
    2903,
    2909,
    2917,
    2927,
    2939,
    2953,
    2957,
    2963,
    2969,
    2971,
    2999,
    3001,
    3011,
    3019,
    3023,
    3037,
    3041,
    3049,
    3061,
    3067,
    3079,
    3083,
    3089,
    3109,
    3119,
    3121,
    3137,
    3163,
    3167,
    3169,
    3181,
    3187,
    3191,
    3203,
    3209,
    3217,
    3221,
    3229,
    3251,
    3253,
    3257,
    3259,
    3271,
    3299,
    3301,
    3307,
    3313,
    3319,
    3323,
    3329,
    3331,
    3343,
    3347,
    3359,
    3361,
    3371,
    3373,
    3389,
    3391,
    3407,
    3413,
    3433,
    3449,
    3457,
    3461,
    3463,
    3467,
    3469,
    3491,
    3499,
    3511,
    3517,
    3527,
    3529,
    3533,
    3539,
    3541,
    3547,
    3557,
    3559,
    3571,
    3581,
    3583,
    3593,
    3607,
    3613,
    3617,
    3623,
    3631,
    3637,
    3643,
    3659,
    3671,
    3673,
    3677,
    3691,
    3697,
    3701,
    3709,
    3719,
    3727,
    3733,
    3739,
    3761,
    3767,
    3769,
    3779,
    3793,
    3797,
    3803,
    3821,
    3823,
    3833,
    3847,
    3851,
    3853,
    3863,
    3877,
    3881,
    3889,
    3907,
    3911,
    3917,
    3919,
    3923,
    3929,
    3931,
    3943,
    3947,
    3967,
    3989,
    4001,
    4003,
    4007,
    4013,
    4019,
    4021,
    4027,
    4049,
    4051,
    4057,
    4073,
    4079,
    4091,
    4093,
    4099,
    4111,
    4127,
    4129,
    4133,
    4139,
    4153,
    4157,
    4159,
    4177,
    4201,
    4211,
    4217,
    4219,
    4229,
    4231,
    4241,
    4243,
    4253,
    4259,
    4261,
    4271,
    4273,
    4283,
    4289,
    4297,
    4327,
    4337,
    4339,
    4349,
    4357,
    4363,
    4373,
    4391,
    4397,
    4409,
    4421,
    4423,
    4441,
    4447,
    4451,
    4457,
    4463,
    4481,
    4483,
    4493,
    4507,
    4513,
    4517,
    4519,
    4523,
    4547,
    4549,
    4561,
    4567,
    4583,
    4591,
    4597,
    4603,
    4621,
    4637,
    4639,
    4643,
    4649,
    4651,
    4657,
    4663,
    4673,
    4679,
    4691,
    4703,
    4721,
    4723,
    4729,
    4733,
    4751,
    4759,
    4783,
    4787,
    4789,
    4793,
    4799,
    4801,
    4813,
    4817,
    4831,
    4861,
    4871,
    4877,
    4889,
    4903,
    4909,
    4919,
    4931,
    4933,
    4937,
    4943,
    4951,
    4957,
    4967,
    4969,
    4973,
    4987,
    4993,
    4999,
    5003,
    5009,
    5011,
    5021,
    5023,
    5039,
    5051,
    5059,
    5077,
    5081,
    5087,
    5099,
    5101,
    5107,
    5113,
    5119,
    5147,
    5153,
    5167,
    5171,
    5179,
    5189,
    5197,
    5209,
    5227,
    5231,
    5233,
    5237,
    5261,
    5273,
    5279,
    5281,
    5297,
    5303,
    5309,
    5323,
    5333,
    5347,
    5351,
    5381,
    5387,
    5393,
    5399,
    5407,
    5413,
    5417,
    5419,
    5431,
    5437,
    5441,
    5443,
    5449,
    5471,
    5477,
    5479,
    5483,
    5501,
    5503,
    5507,
    5519,
    5521,
    5527,
    5531,
    5557,
    5563,
    5569,
    5573,
    5581,
    5591,
    5623,
    5639,
    5641,
    5647,
    5651,
    5653,
    5657,
    5659,
    5669,
    5683,
    5689,
    5693,
    5701,
    5711,
    5717,
    5737,
    5741,
    5743,
    5749,
    5779,
    5783,
    5791,
    5801,
    5807,
    5813,
    5821,
    5827,
    5839,
    5843,
    5849,
    5851,
    5857,
    5861,
    5867,
    5869,
    5879,
    5881,
    5897,
    5903,
    5923,
    5927,
    5939,
    5953,
    5981,
    5987,
    6007,
    6011,
    6029,
    6037,
    6043,
    6047,
    6053,
    6067,
    6073,
    6079,
    6089,
    6091,
    6101,
    6113,
    6121,
    6131,
    6133,
    6143,
    6151,
    6163,
    6173,
    6197,
    6199,
    6203,
    6211,
    6217,
    6221,
    6229,
    6247,
    6257,
    6263,
    6269,
    6271,
    6277,
    6287,
    6299,
    6301,
    6311,
    6317,
    6323,
    6329,
    6337,
    6343,
    6353,
    6359,
    6361,
    6367,
    6373,
    6379,
    6389,
    6397,
    6421,
    6427,
    6449,
    6451,
    6469,
    6473,
    6481,
    6491,
    6521,
    6529,
    6547,
    6551,
    6553,
    6563,
    6569,
    6571,
    6577,
    6581,
    6599,
    6607,
    6619,
    6637,
    6653,
    6659,
    6661,
    6673,
    6679,
    6689,
    6691,
    6701,
    6703,
    6709,
    6719,
    6733,
    6737,
    6761,
    6763,
    6779,
    6781,
    6791,
    6793,
    6803,
    6823,
    6827,
    6829,
    6833,
    6841,
    6857,
    6863,
    6869,
    6871,
    6883,
    6899,
    6907,
    6911,
    6917,
    6947,
    6949,
    6959,
    6961,
    6967,
    6971,
    6977,
    6983,
    6991,
    6997,
    7001,
    7013,
    7019,
    7027,
    7039,
    7043,
    7057,
    7069,
    7079,
    7103,
    7109,
    7121,
    7127,
    7129,
    7151,
    7159,
    7177,
    7187,
    7193,
    7207,
    7211,
    7213,
    7219,
    7229,
    7237,
    7243,
    7247,
    7253,
    7283,
    7297,
    7307,
    7309,
    7321,
    7331,
    7333,
    7349,
    7351,
    7369,
    7393,
    7411,
    7417,
    7433,
    7451,
    7457,
    7459,
    7477,
    7481,
    7487,
    7489,
    7499,
    7507,
    7517,
    7523,
    7529,
    7537,
    7541,
    7547,
    7549,
    7559,
    7561,
    7573,
    7577,
    7583,
    7589,
    7591,
    7603,
    7607,
    7621,
    7639,
    7643,
    7649,
    7669,
    7673,
    7681,
    7687,
    7691,
    7699,
    7703,
    7717,
    7723,
    7727,
    7741,
    7753,
    7757,
    7759,
    7789,
    7793,
    7817,
    7823,
    7829,
    7841,
    7853,
    7867,
    7873,
    7877,
    7879,
    7883,
    7901,
    7907,
    7919,
    7927,
    7933,
    7937,
    7949,
    7951,
    7963,
    7993,
    8009,
    8011,
    8017,
    8039,
    8053,
    8059,
    8069,
    8081,
    8087,
    8089,
    8093,
    8101,
    8111,
    8117,
    8123,
    8147,
    8161,
    8167,
    8171,
    8179,
    8191,
    8209,
    8219,
    8221,
    8231,
    8233,
    8237,
    8243,
    8263,
    8269,
    8273,
    8287,
    8291,
    8293,
    8297,
    8311,
    8317,
    8329,
    8353,
    8363,
    8369,
    8377,
    8387,
    8389,
    8419,
    8423,
    8429,
    8431,
    8443,
    8447,
    8461,
    8467,
    8501,
    8513,
    8521,
    8527,
    8537,
    8539,
    8543,
    8563,
    8573,
    8581,
    8597,
    8599,
    8609,
    8623,
    8627,
    8629,
    8641,
    8647,
    8663,
    8669,
    8677,
    8681,
    8689,
    8693,
    8699,
    8707,
    8713,
    8719,
    8731,
    8737,
    8741,
    8747,
    8753,
    8761,
    8779,
    8783,
    8803,
    8807,
    8819,
    8821,
    8831,
    8837,
    8839,
    8849,
    8861,
    8863,
    8867,
    8887,
    8893,
    8923,
    8929,
    8933,
    8941,
    8951,
    8963,
    8969,
    8971,
    8999,
    9001,
    9007,
    9011,
    9013,
    9029,
    9041,
    9043,
    9049,
    9059,
    9067,
    9091,
    9103,
    9109,
    9127,
    9133,
    9137,
    9151,
    9157,
    9161,
    9173,
    9181,
    9187,
    9199,
    9203,
    9209,
    9221,
    9227,
    9239,
    9241,
    9257,
    9277,
    9281,
    9283,
    9293,
    9311,
    9319,
    9323,
    9337,
    9341,
    9343,
    9349,
    9371,
    9377,
    9391,
    9397,
    9403,
    9413,
    9419,
    9421,
    9431,
    9433,
    9437,
    9439,
    9461,
    9463,
    9467,
    9473,
    9479,
    9491,
    9497,
    9511,
    9521,
    9533,
    9539,
    9547,
    9551,
    9587,
    9601,
    9613,
    9619,
    9623,
    9629,
    9631,
    9643,
    9649,
    9661,
    9677,
    9679,
    9689,
    9697,
    9719,
    9721,
    9733,
    9739,
    9743,
    9749,
    9767,
    9769,
    9781,
    9787,
    9791,
    9803,
    9811,
    9817,
    9829,
    9833,
    9839,
    9851,
    9857,
    9859,
    9871,
    9883,
    9887,
    9901,
    9907,
    9923,
    9929,
    9931,
    9941,
    9949,
    9967,
    9973,
    10007,
    10009,
    10037,
    10039,
    10061,
    10067,
    10069,
    10079,
    10091,
    10093,
    10099,
    10103,
    10111,
    10133,
    10139,
    10141,
    10151,
    10159,
    10163,
    10169,
    10177,
    10181,
    10193,
    10211,
    10223,
    10243,
    10247,
    10253,
    10259,
    10267,
    10271,
    10273,
    10289,
    10301,
    10303,
    10313,
    10321,
    10331,
    10333,
    10337,
    10343,
    10357,
    10369,
    10391,
    10399,
    10427,
    10429,
    10433,
    10453,
    10457,
    10459,
    10463,
    10477,
    10487,
    10499,
    10501,
    10513,
    10529,
    10531,
    10559,
    10567,
    10589,
    10597,
    10601,
    10607,
    10613,
    10627,
    10631,
    10639,
    10651,
    10657,
    10663,
    10667,
    10687,
    10691,
    10709,
    10711,
    10723,
    10729,
    10733,
    10739,
    10753,
    10771,
    10781,
    10789,
    10799,
    10831,
    10837,
    10847,
    10853,
    10859,
    10861,
    10867,
    10883,
    10889,
    10891,
    10903,
    10909,
    10937,
    10939,
    10949,
    10957,
    10973,
    10979,
    10987,
    10993,
    11003,
    11027,
    11047,
    11057,
    11059,
    11069,
    11071,
    11083,
    11087,
    11093,
    11113,
    11117,
    11119,
    11131,
    11149,
    11159,
    11161,
    11171,
    11173,
    11177,
    11197,
    11213,
    11239,
    11243,
    11251,
    11257,
    11261,
    11273,
    11279,
    11287,
    11299,
    11311,
    11317,
    11321,
    11329,
    11351,
    11353,
    11369,
    11383,
    11393,
    11399,
    11411,
    11423,
    11437,
    11443,
    11447,
    11467,
    11471,
    11483,
    11489,
    11491,
    11497,
    11503,
    11519,
    11527,
    11549,
    11551,
    11579,
    11587,
    11593,
    11597,
    11617,
    11621,
    11633,
    11657,
    11677,
    11681,
    11689,
    11699,
    11701,
    11717,
    11719,
    11731,
    11743,
    11777,
    11779,
    11783,
    11789,
    11801,
    11807,
    11813,
    11821,
    11827,
    11831,
    11833,
    11839,
    11863,
    11867,
    11887,
    11897,
    11903,
    11909,
    11923,
    11927,
    11933,
    11939,
    11941,
    11953,
    11959,
    11969,
    11971,
    11981,
    11987,
    12007,
    12011,
    12037,
    12041,
    12043,
    12049,
    12071,
    12073,
    12097,
    12101,
    12107,
    12109,
    12113,
    12119,
    12143,
    12149,
    12157,
    12161,
    12163,
    12197,
    12203,
    12211,
    12227,
    12239,
    12241,
    12251,
    12253,
    12263,
    12269,
    12277,
    12281,
    12289,
    12301,
    12323,
    12329,
    12343,
    12347,
    12373,
    12377,
    12379,
    12391,
    12401,
    12409,
    12413,
    12421,
    12433,
    12437,
    12451,
    12457,
    12473,
    12479,
    12487,
    12491,
    12497,
    12503,
    12511,
    12517,
    12527,
    12539,
    12541,
    12547,
    12553,
    12569,
    12577,
    12583,
    12589,
    12601,
    12611,
    12613,
    12619,
    12637,
    12641,
    12647,
    12653,
    12659,
    12671,
    12689,
    12697,
    12703,
    12713,
    12721,
    12739,
    12743,
    12757,
    12763,
    12781,
    12791,
    12799,
    12809,
    12821,
    12823,
    12829,
    12841,
    12853,
    12889,
    12893,
    12899,
    12907,
    12911,
    12917,
    12919,
    12923,
    12941,
    12953,
    12959,
    12967,
    12973,
    12979,
    12983,
    13001,
    13003,
    13007,
    13009,
    13033,
    13037,
    13043,
    13049,
    13063,
    13093,
    13099,
    13103,
    13109,
    13121,
    13127,
    13147,
    13151,
    13159,
    13163,
    13171,
    13177,
    13183,
    13187,
    13217,
    13219,
    13229,
    13241,
    13249,
    13259,
    13267,
    13291,
    13297,
    13309,
    13313,
    13327,
    13331,
    13337,
    13339,
    13367,
    13381,
    13397,
    13399,
    13411,
    13417,
    13421,
    13441,
    13451,
    13457,
    13463,
    13469,
    13477,
    13487,
    13499,
    13513,
    13523,
    13537,
    13553,
    13567,
    13577,
    13591,
    13597,
    13613,
    13619,
    13627,
    13633,
    13649,
    13669,
    13679,
    13681,
    13687,
    13691,
    13693,
    13697,
    13709,
    13711,
    13721,
    13723,
    13729,
    13751,
    13757,
    13759,
    13763,
    13781,
    13789,
    13799,
    13807,
    13829,
    13831,
    13841,
    13859,
    13873,
    13877,
    13879,
    13883,
    13901,
    13903,
    13907,
    13913,
    13921,
    13931,
    13933,
    13963,
    13967,
    13997,
    13999,
    14009,
    14011,
    14029,
    14033,
    14051,
    14057,
    14071,
    14081,
    14083,
    14087,
    14107,
    14143,
    14149,
    14153,
    14159,
    14173,
    14177,
    14197,
    14207,
    14221,
    14243,
    14249,
    14251,
    14281,
    14293,
    14303,
    14321,
    14323,
    14327,
    14341,
    14347,
    14369,
    14387,
    14389,
    14401,
    14407,
    14411,
    14419,
    14423,
    14431,
    14437,
    14447,
    14449,
    14461,
    14479,
    14489,
    14503,
    14519,
    14533,
    14537,
    14543,
    14549,
    14551,
    14557,
    14561,
    14563,
    14591,
    14593,
    14621,
    14627,
    14629,
    14633,
    14639,
    14653,
    14657,
    14669,
    14683,
    14699,
    14713,
    14717,
    14723,
    14731,
    14737,
    14741,
    14747,
    14753,
    14759,
    14767,
    14771,
    14779,
    14783,
    14797,
    14813,
    14821,
    14827,
    14831,
    14843,
    14851,
    14867,
    14869,
    14879,
    14887,
    14891,
    14897,
    14923,
    14929,
    14939,
    14947,
    14951,
    14957,
    14969,
    14983,
    15013,
    15017,
    15031,
    15053,
    15061,
    15073,
    15077,
    15083,
    15091,
    15101,
    15107,
    15121,
    15131,
    15137,
    15139,
    15149,
    15161,
    15173,
    15187,
    15193,
    15199,
    15217,
    15227,
    15233,
    15241,
    15259,
    15263,
    15269,
    15271,
    15277,
    15287,
    15289,
    15299,
    15307,
    15313,
    15319,
    15329,
    15331,
    15349,
    15359,
    15361,
    15373,
    15377,
    15383,
    15391,
    15401,
    15413,
    15427,
    15439,
    15443,
    15451,
    15461,
    15467,
    15473,
    15493,
    15497,
    15511,
    15527,
    15541,
    15551,
    15559,
    15569,
    15581,
    15583,
    15601,
    15607,
    15619,
    15629,
    15641,
    15643,
    15647,
    15649,
    15661,
    15667,
    15671,
    15679,
    15683,
    15727,
    15731,
    15733,
    15737,
    15739,
    15749,
    15761,
    15767,
    15773,
    15787,
    15791,
    15797,
    15803,
    15809,
    15817,
    15823,
    15859,
    15877,
    15881,
    15887,
    15889,
    15901,
    15907,
    15913,
    15919,
    15923,
    15937,
    15959,
    15971,
    15973,
    15991,
    16001,
    16007,
    16033,
    16057,
    16061,
    16063,
    16067,
    16069,
    16073,
    16087,
    16091,
    16097,
    16103,
    16111,
    16127,
    16139,
    16141,
    16183,
    16187,
    16189,
    16193,
    16217,
    16223,
    16229,
    16231,
    16249,
    16253,
    16267,
    16273,
    16301,
    16319,
    16333,
    16339,
    16349,
    16361,
    16363,
    16369,
    16381,
    16411,
    16417,
    16421,
    16427,
    16433,
    16447,
    16451,
    16453,
    16477,
    16481,
    16487,
    16493,
    16519,
    16529,
    16547,
    16553,
    16561,
    16567,
    16573,
    16603,
    16607,
    16619,
    16631,
    16633,
    16649,
    16651,
    16657,
    16661,
    16673,
    16691,
    16693,
    16699,
    16703,
    16729,
    16741,
    16747,
    16759,
    16763,
    16787,
    16811,
    16823,
    16829,
    16831,
    16843,
    16871,
    16879,
    16883,
    16889,
    16901,
    16903,
    16921,
    16927,
    16931,
    16937,
    16943,
    16963,
    16979,
    16981,
    16987,
    16993,
    17011,
    17021,
    17027,
    17029,
    17033,
    17041,
    17047,
    17053,
    17077,
    17093,
    17099,
    17107,
    17117,
    17123,
    17137,
    17159,
    17167,
    17183,
    17189,
    17191,
    17203,
    17207,
    17209,
    17231,
    17239,
    17257,
    17291,
    17293,
    17299,
    17317,
    17321,
    17327,
    17333,
    17341,
    17351,
    17359,
    17377,
    17383,
    17387,
    17389,
    17393,
    17401,
    17417,
    17419,
    17431,
    17443,
    17449,
    17467,
    17471,
    17477,
    17483,
    17489,
    17491,
    17497,
    17509,
    17519,
    17539,
    17551,
    17569,
    17573,
    17579,
    17581,
    17597,
    17599,
    17609,
    17623,
    17627,
    17657,
    17659,
    17669,
    17681,
    17683,
    17707,
    17713,
    17729,
    17737,
    17747,
    17749,
    17761,
    17783,
    17789,
    17791,
    17807,
    17827,
    17837,
    17839,
    17851,
    17863,
    17881,
    17891,
    17903,
    17909,
    17911,
    17921,
    17923,
    17929,
    17939,
    17957,
    17959,
    17971,
    17977,
    17981,
    17987,
    17989,
    18013,
    18041,
    18043,
    18047,
    18049,
    18059,
    18061,
    18077,
    18089,
    18097,
    18119,
    18121,
    18127,
    18131,
    18133,
    18143,
    18149,
    18169,
    18181,
    18191,
    18199,
    18211,
    18217,
    18223,
    18229,
    18233,
    18251,
    18253,
    18257,
    18269,
    18287,
    18289,
    18301,
    18307,
    18311,
    18313,
    18329,
    18341,
    18353,
    18367,
    18371,
    18379,
    18397,
    18401,
    18413,
    18427,
    18433,
    18439,
    18443,
    18451,
    18457,
    18461,
    18481,
    18493,
    18503,
    18517,
    18521,
    18523,
    18539,
    18541,
    18553,
    18583,
    18587,
    18593,
    18617,
    18637,
    18661,
    18671,
    18679,
    18691,
    18701,
    18713,
    18719,
    18731,
    18743,
    18749,
    18757,
    18773,
    18787,
    18793,
    18797,
    18803,
    18839,
    18859,
    18869,
    18899,
    18911,
    18913,
    18917,
    18919,
    18947,
    18959,
    18973,
    18979,
    19001,
    19009,
    19013,
    19031,
    19037,
    19051,
    19069,
    19073,
    19079,
    19081,
    19087,
    19121,
    19139,
    19141,
    19157,
    19163,
    19181,
    19183,
    19207,
    19211,
    19213,
    19219,
    19231,
    19237,
    19249,
    19259,
    19267,
    19273,
    19289,
    19301,
    19309,
    19319,
    19333,
    19373,
    19379,
    19381,
    19387,
    19391,
    19403,
    19417,
    19421,
    19423,
    19427,
    19429,
    19433,
    19441,
    19447,
    19457,
    19463,
    19469,
    19471,
    19477,
    19483,
    19489,
    19501,
    19507,
    19531,
    19541,
    19543,
    19553,
    19559,
    19571,
    19577,
    19583,
    19597,
    19603,
    19609,
    19661,
    19681,
    19687,
    19697,
    19699,
    19709,
    19717,
    19727,
    19739,
    19751,
    19753,
    19759,
    19763,
    19777,
    19793,
    19801,
    19813,
    19819,
    19841,
    19843,
    19853,
    19861,
    19867,
    19889,
    19891,
    19913,
    19919,
    19927,
    19937,
    19949,
    19961,
    19963,
    19973,
    19979,
    19991,
    19993,
    19997,
    20011,
    20021,
    20023,
    20029,
    20047,
    20051,
    20063,
    20071,
    20089,
    20101,
    20107,
    20113,
    20117,
    20123,
    20129,
    20143,
    20147,
    20149,
    20161,
    20173,
    20177,
    20183,
    20201,
    20219,
    20231,
    20233,
    20249,
    20261,
    20269,
    20287,
    20297,
    20323,
    20327,
    20333,
    20341,
    20347,
    20353,
    20357,
    20359,
    20369,
    20389,
    20393,
    20399,
    20407,
    20411,
    20431,
    20441,
    20443,
    20477,
    20479,
    20483,
    20507,
    20509,
    20521,
    20533,
    20543,
    20549,
    20551,
    20563,
    20593,
    20599,
    20611,
    20627,
    20639,
    20641,
    20663,
    20681,
    20693,
    20707,
    20717,
    20719,
    20731,
    20743,
    20747,
    20749,
    20753,
    20759,
    20771,
    20773,
    20789,
    20807,
    20809,
    20849,
    20857,
    20873,
    20879,
    20887,
    20897,
    20899,
    20903,
    20921,
    20929,
    20939,
    20947,
    20959,
    20963,
    20981,
    20983,
    21001,
    21011,
    21013,
    21017,
    21019,
    21023,
    21031,
    21059,
    21061,
    21067,
    21089,
    21101,
    21107,
    21121,
    21139,
    21143,
    21149,
    21157,
    21163,
    21169,
    21179,
    21187,
    21191,
    21193,
    21211,
    21221,
    21227,
    21247,
    21269,
    21277,
    21283,
    21313,
    21317,
    21319,
    21323,
    21341,
    21347,
    21377,
    21379,
    21383,
    21391,
    21397,
    21401,
    21407,
    21419,
    21433,
    21467,
    21481,
    21487,
    21491,
    21493,
    21499,
    21503,
    21517,
    21521,
    21523,
    21529,
    21557,
    21559,
    21563,
    21569,
    21577,
    21587,
    21589,
    21599,
    21601,
    21611,
    21613,
    21617,
    21647,
    21649,
    21661,
    21673,
    21683,
    21701,
    21713,
    21727,
    21737,
    21739,
    21751,
    21757,
    21767,
    21773,
    21787,
    21799,
    21803,
    21817,
    21821,
    21839,
    21841,
    21851,
    21859,
    21863,
    21871,
    21881,
    21893,
    21911,
    21929,
    21937,
    21943,
    21961,
    21977,
    21991,
    21997,
    22003,
    22013,
    22027,
    22031,
    22037,
    22039,
    22051,
    22063,
    22067,
    22073,
    22079,
    22091,
    22093,
    22109,
    22111,
    22123,
    22129,
    22133,
    22147,
    22153,
    22157,
    22159,
    22171,
    22189,
    22193,
    22229,
    22247,
    22259,
    22271,
    22273,
    22277,
    22279,
    22283,
    22291,
    22303,
    22307,
    22343,
    22349,
    22367,
    22369,
    22381,
    22391,
    22397,
    22409,
    22433,
    22441,
    22447,
    22453,
    22469,
    22481,
    22483,
    22501,
    22511,
    22531,
    22541,
    22543,
    22549,
    22567,
    22571,
    22573,
    22613,
    22619,
    22621,
    22637,
    22639,
    22643,
    22651,
    22669,
    22679,
    22691,
    22697,
    22699,
    22709,
    22717,
    22721,
    22727,
    22739,
    22741,
    22751,
    22769,
    22777,
    22783,
    22787,
    22807,
    22811,
    22817,
    22853,
    22859,
    22861,
    22871,
    22877,
    22901,
    22907,
    22921,
    22937,
    22943,
    22961,
    22963,
    22973,
    22993,
    23003,
    23011,
    23017,
    23021,
    23027,
    23029,
    23039,
    23041,
    23053,
    23057,
    23059,
    23063,
    23071,
    23081,
    23087,
    23099,
    23117,
    23131,
    23143,
    23159,
    23167,
    23173,
    23189,
    23197,
    23201,
    23203,
    23209,
    23227,
    23251,
    23269,
    23279,
    23291,
    23293,
    23297,
    23311,
    23321,
    23327,
    23333,
    23339,
    23357,
    23369,
    23371,
    23399,
    23417,
    23431,
    23447,
    23459,
    23473,
    23497,
    23509,
    23531,
    23537,
    23539,
    23549,
    23557,
    23561,
    23563,
    23567,
    23581,
    23593,
    23599,
    23603,
    23609,
    23623,
    23627,
    23629,
    23633,
    23663,
    23669,
    23671,
    23677,
    23687,
    23689,
    23719,
    23741,
    23743,
    23747,
    23753,
    23761,
    23767,
    23773,
    23789,
    23801,
    23813,
    23819,
    23827,
    23831,
    23833,
    23857,
    23869,
    23873,
    23879,
    23887,
    23893,
    23899,
    23909,
    23911,
    23917,
    23929,
    23957,
    23971,
    23977,
    23981,
    23993,
    24001,
    24007,
    24019,
    24023,
    24029,
    24043,
    24049,
    24061,
    24071,
    24077,
    24083,
    24091,
    24097,
    24103,
    24107,
    24109,
    24113,
    24121,
    24133,
    24137,
    24151,
    24169,
    24179,
    24181,
    24197,
    24203,
    24223,
    24229,
    24239,
    24247,
    24251,
    24281,
    24317,
    24329,
    24337,
    24359,
    24371,
    24373,
    24379,
    24391,
    24407,
    24413,
    24419,
    24421,
    24439,
    24443,
    24469,
    24473,
    24481,
    24499,
    24509,
    24517,
    24527,
    24533,
    24547,
    24551,
    24571,
    24593,
    24611,
    24623,
    24631,
    24659,
    24671,
    24677,
    24683,
    24691,
    24697,
    24709,
    24733,
    24749,
    24763,
    24767,
    24781,
    24793,
    24799,
    24809,
    24821,
    24841,
    24847,
    24851,
    24859,
    24877,
    24889,
    24907,
    24917,
    24919,
    24923,
    24943,
    24953,
    24967,
    24971,
    24977,
    24979,
    24989,
    25013,
    25031,
    25033,
    25037,
    25057,
    25073,
    25087,
    25097,
    25111,
    25117,
    25121,
    25127,
    25147,
    25153,
    25163,
    25169,
    25171,
    25183,
    25189,
    25219,
    25229,
    25237,
    25243,
    25247,
    25253,
    25261,
    25301,
    25303,
    25307,
    25309,
    25321,
    25339,
    25343,
    25349,
    25357,
    25367,
    25373,
    25391,
    25409,
    25411,
    25423,
    25439,
    25447,
    25453,
    25457,
    25463,
    25469,
    25471,
    25523,
    25537,
    25541,
    25561,
    25577,
    25579,
    25583,
    25589,
    25601,
    25603,
    25609,
    25621,
    25633,
    25639,
    25643,
    25657,
    25667,
    25673,
    25679,
    25693,
    25703,
    25717,
    25733,
    25741,
    25747,
    25759,
    25763,
    25771,
    25793,
    25799,
    25801,
    25819,
    25841,
    25847,
    25849,
    25867,
    25873,
    25889,
    25903,
    25913,
    25919,
    25931,
    25933,
    25939,
    25943,
    25951,
    25969,
    25981,
    25997,
    25999,
    26003,
    26017,
    26021,
    26029,
    26041,
    26053,
    26083,
    26099,
    26107,
    26111,
    26113,
    26119,
    26141,
    26153,
    26161,
    26171,
    26177,
    26183,
    26189,
    26203,
    26209,
    26227,
    26237,
    26249,
    26251,
    26261,
    26263,
    26267,
    26293,
    26297,
    26309,
    26317,
    26321,
    26339,
    26347,
    26357,
    26371,
    26387,
    26393,
    26399,
    26407,
    26417,
    26423,
    26431,
    26437,
    26449,
    26459,
    26479,
    26489,
    26497,
    26501,
    26513,
    26539,
    26557,
    26561,
    26573,
    26591,
    26597,
    26627,
    26633,
    26641,
    26647,
    26669,
    26681,
    26683,
    26687,
    26693,
    26699,
    26701,
    26711,
    26713,
    26717,
    26723,
    26729,
    26731,
    26737,
    26759,
    26777,
    26783,
    26801,
    26813,
    26821,
    26833,
    26839,
    26849,
    26861,
    26863,
    26879,
    26881,
    26891,
    26893,
    26903,
    26921,
    26927,
    26947,
    26951,
    26953,
    26959,
    26981,
    26987,
    26993,
    27011,
    27017,
    27031,
    27043,
    27059,
    27061,
    27067,
    27073,
    27077,
    27091,
    27103,
    27107,
    27109,
    27127,
    27143,
    27179,
    27191,
    27197,
    27211,
    27239,
    27241,
    27253,
    27259,
    27271,
    27277,
    27281,
    27283,
    27299,
    27329,
    27337,
    27361,
    27367,
    27397,
    27407,
    27409,
    27427,
    27431,
    27437,
    27449,
    27457,
    27479,
    27481,
    27487,
    27509,
    27527,
    27529,
    27539,
    27541,
    27551,
    27581,
    27583,
    27611,
    27617,
    27631,
    27647,
    27653,
    27673,
    27689,
    27691,
    27697,
    27701,
    27733,
    27737,
    27739,
    27743,
    27749,
    27751,
    27763,
    27767,
    27773,
    27779,
    27791,
    27793,
    27799,
    27803,
    27809,
    27817,
    27823,
    27827,
    27847,
    27851,
    27883,
    27893,
    27901,
    27917,
    27919,
    27941,
    27943,
    27947,
    27953,
    27961,
    27967,
    27983,
    27997,
    28001,
    28019,
    28027,
    28031,
    28051,
    28057,
    28069,
    28081,
    28087,
    28097,
    28099,
    28109,
    28111,
    28123,
    28151,
    28163,
    28181,
    28183,
    28201,
    28211,
    28219,
    28229,
    28277,
    28279,
    28283,
    28289,
    28297,
    28307,
    28309,
    28319,
    28349,
    28351,
    28387,
    28393,
    28403,
    28409,
    28411,
    28429,
    28433,
    28439,
    28447,
    28463,
    28477,
    28493,
    28499,
    28513,
    28517,
    28537,
    28541,
    28547,
    28549,
    28559,
    28571,
    28573,
    28579,
    28591,
    28597,
    28603,
    28607,
    28619,
    28621,
    28627,
    28631,
    28643,
    28649,
    28657,
    28661,
    28663,
    28669,
    28687,
    28697,
    28703,
    28711,
    28723,
    28729,
    28751,
    28753,
    28759,
    28771,
    28789,
    28793,
    28807,
    28813,
    28817,
    28837,
    28843,
    28859,
    28867,
    28871,
    28879,
    28901,
    28909,
    28921,
    28927,
    28933,
    28949,
    28961,
    28979,
    29009,
    29017,
    29021,
    29023,
    29027,
    29033,
    29059,
    29063,
    29077,
    29101,
    29123,
    29129,
    29131,
    29137,
    29147,
    29153,
    29167,
    29173,
    29179,
    29191,
    29201,
    29207,
    29209,
    29221,
    29231,
    29243,
    29251,
    29269,
    29287,
    29297,
    29303,
    29311,
    29327,
    29333,
    29339,
    29347,
    29363,
    29383,
    29387,
    29389,
    29399,
    29401,
    29411,
    29423,
    29429,
    29437,
    29443,
    29453,
    29473,
    29483,
    29501,
    29527,
    29531,
    29537,
    29567,
    29569,
    29573,
    29581,
    29587,
    29599,
    29611,
    29629,
    29633,
    29641,
    29663,
    29669,
    29671,
    29683,
    29717,
    29723,
    29741,
    29753,
    29759,
    29761,
    29789,
    29803,
    29819,
    29833,
    29837,
    29851,
    29863,
    29867,
    29873,
    29879,
    29881,
    29917,
    29921,
    29927,
    29947,
    29959,
    29983,
    29989,
    30011,
    30013,
    30029,
    30047,
    30059,
    30071,
    30089,
    30091,
    30097,
    30103,
    30109,
    30113,
    30119,
    30133,
    30137,
    30139,
    30161,
    30169,
    30181,
    30187,
    30197,
    30203,
    30211,
    30223,
    30241,
    30253,
    30259,
    30269,
    30271,
    30293,
    30307,
    30313,
    30319,
    30323,
    30341,
    30347,
    30367,
    30389,
    30391,
    30403,
    30427,
    30431,
    30449,
    30467,
    30469,
    30491,
    30493,
    30497,
    30509,
    30517,
    30529,
    30539,
    30553,
    30557,
    30559,
    30577,
    30593,
    30631,
    30637,
    30643,
    30649,
    30661,
    30671,
    30677,
    30689,
    30697,
    30703,
    30707,
    30713,
    30727,
    30757,
    30763,
    30773,
    30781,
    30803,
    30809,
    30817,
    30829,
    30839,
    30841,
    30851,
    30853,
    30859,
    30869,
    30871,
    30881,
    30893,
    30911,
    30931,
    30937,
    30941,
    30949,
    30971,
    30977,
    30983,
    31013,
    31019,
    31033,
    31039,
    31051,
    31063,
    31069,
    31079,
    31081,
    31091,
    31121,
    31123,
    31139,
    31147,
    31151,
    31153,
    31159,
    31177,
    31181,
    31183,
    31189,
    31193,
    31219,
    31223,
    31231,
    31237,
    31247,
    31249,
    31253,
    31259,
    31267,
    31271,
    31277,
    31307,
    31319,
    31321,
    31327,
    31333,
    31337,
    31357,
    31379,
    31387,
    31391,
    31393,
    31397,
    31469,
    31477,
    31481,
    31489,
    31511,
    31513,
    31517,
    31531,
    31541,
    31543,
    31547,
    31567,
    31573,
    31583,
    31601,
    31607,
    31627,
    31643,
    31649,
    31657,
    31663,
    31667,
    31687,
    31699,
    31721,
    31723,
    31727,
    31729,
    31741,
    31751,
    31769,
    31771,
    31793,
    31799,
    31817,
    31847,
    31849,
    31859,
    31873,
    31883,
    31891,
    31907,
    31957,
    31963,
    31973,
    31981,
    31991,
    32003,
    32009,
    32027,
    32029,
    32051,
    32057,
    32059,
    32063,
    32069,
    32077,
    32083,
    32089,
    32099,
    32117,
    32119,
    32141,
    32143,
    32159,
    32173,
    32183,
    32189,
    32191,
    32203,
    32213,
    32233,
    32237,
    32251,
    32257,
    32261,
    32297,
    32299,
    32303,
    32309,
    32321,
    32323,
    32327,
    32341,
    32353,
    32359,
    32363,
    32369,
    32371,
    32377,
    32381,
    32401,
    32411,
    32413,
    32423,
    32429,
    32441,
    32443,
    32467,
    32479,
    32491,
    32497,
    32503,
    32507,
    32531,
    32533,
    32537,
    32561,
    32563,
    32569,
    32573,
    32579,
    32587,
    32603,
    32609,
    32611,
    32621,
    32633,
    32647,
    32653,
    32687,
    32693,
    32707,
    32713,
    32717,
    32719 /*,  0*/ // this number (0) appears at the end of the tables in all exe's, but the table size is calculated as not
                   // including this?? unless its producing code that checks for numbers above?
};

static int Prime_Compare_Func(const void *a, const void *b)
{
    if (*static_cast<const mp_digit_u *>(a) < *static_cast<const uint16_t *>(b)) {
        return 1;
    } else if (*static_cast<const mp_digit_u *>(a) > *static_cast<const uint16_t *>(b)) {
        return -1;
    }

    return 0;
}

int32_t MPMath::Byte_Precision(int32_t length)
{
    DEBUG_ASSERT(length > 0);

    int32_t bytes = BYTES_PER_UNIT;

    for (int bits = 24; bits != -8; bits -= 8) {
        if ((length >> bits) != 0) {
            break;
        }

        --bytes;
    }

    return bytes;
}

int32_t MPMath::Significance(const mp_digit_u *number, int32_t precision)
{
    DEBUG_ASSERT(number != nullptr);
    DEBUG_ASSERT(precision > 0);

    int32_t i = precision - 1;

    while ((i >= 0) && (number[i] == 0)) {
        i--;
    }

    return i + 1;
}

int32_t MPMath::Count_Bits(const mp_digit_u *number, int32_t precision)
{
    DEBUG_ASSERT(number != nullptr);
    DEBUG_ASSERT(precision > 0);

    int32_t bits = Significance(number, precision);

    if (bits) {
        uint32_t bitmask = 0x80000000;
        mp_digit_u sigint = number[bits - 1];
        bits *= 32;

        while ((bitmask & sigint) == 0) {
            bitmask >>= 1;
            --bits;
        }
    }

    return bits;
}

int32_t MPMath::Count_Bytes(mp_digit_u *number, int32_t precision)
{
    DEBUG_ASSERT(number != nullptr);
    DEBUG_ASSERT(precision > 0);

    uint8_t *byteptr = reinterpret_cast<uint8_t *>(number);
    int32_t total_bytes = Units_To_Bytes(precision);
    int32_t count = 0;

    if (total_bytes) {
        for (int i = 0; i < total_bytes; ++i) {
            if (byteptr[i] == 0) {
                break;
            }

            ++count;
        }
    }

    return count;
}

void MPMath::Init(mp_digit_u *number, mp_digit_u value, int32_t precision)
{
    DEBUG_ASSERT(number != nullptr);
    DEBUG_ASSERT(precision > 0);

    memset(number, 0, precision * BYTES_PER_UNIT);
    *number = value;
}

void MPMath::Move(mp_digit_u *dest, const mp_digit_u *source, int32_t precision)
{
    memcpy(dest, source, precision * BYTES_PER_UNIT);
}

void MPMath::Move_HTOLE(mp_digit_u *dst, const mp_digit_u *src, int32_t precision)
{
    for (int i = 0; i < precision; ++i) {
        dst[i] = htolexmp(src[i]);
    }
}

void MPMath::Move_LETOH(mp_digit_u *dst, const mp_digit_u *src, int32_t precision)
{
    for (int i = 0; i < precision; ++i) {
        dst[i] = lexmptoh(src[i]);
    }
}

void MPMath::Move_HTOBE(mp_digit_u *dst, const mp_digit_u *src, int32_t precision)
{
    for (int i = 0; i < precision; ++i) {
        dst[i] = htobexmp(src[precision - i - 1]);
    }
}

void MPMath::Move_BETOH(mp_digit_u *dst, const mp_digit_u *src, int32_t precision)
{
    for (int i = 0; i < precision; ++i) {
        dst[i] = bexmptoh(src[precision - i - 1]);
    }
}

int32_t MPMath::DER_Length_Encode(uint32_t length, uint8_t *output)
{
    DEBUG_ASSERT(output != nullptr);

    int32_t retval;

    if (length > 127) { // Using long form of length in min number of octets
        retval = 1;
        *output = Byte_Precision(length) | 128;

        for (int i = Byte_Precision(length); i; --i) {
            *(retval++ + output) = length >> (8 * i - 8);
        }
    } else { // Using short form of length, just record length.
        *output = length;
        retval = 1;
    }

    return retval;
}

uint32_t MPMath::Encode(uint8_t *to, const mp_digit_u *from, int32_t precision)
{
    DEBUG_ASSERT(to != nullptr);
    DEBUG_ASSERT(from != nullptr);
    DEBUG_ASSERT(precision > 0);

    // TODO rewrite the function to swap to BE initially, keeps the maths a bit
    // simpler.
    mp_digit_u buffer[MAX_UNIT_PRECISION];
    Move_HTOLE(buffer, from, precision);

    const uint8_t *getp = reinterpret_cast<const uint8_t *>(buffer);
    uint8_t sign = from[precision - 1] & 0x80000000 ? 0xFF : 0x00;

    // i needs to be preserved outside the first loop
    int i;

    //
    // Start at the end of the number as we store chunks in little endian format
    // Scans backward for the first byte that isn't the sign byte.
    //
    for (i = BYTES_PER_UNIT * precision - BYTES_PER_UNIT; i > 0; --i) {
        if (getp[i] != sign) {
            break;
        }
    }

    int putpos = 0;

    //
    // We check if the current byte is the same sign type as the sign, if not,
    // put the sign byte into the encoded destination
    //
    if ((getp[i] >= 0x80 && sign == 0x00) || (getp[i] < 0x80 && sign == 0xFF)) {
        to[putpos++] = sign;
    }

    //
    // Write the remaining bytes to the buffer in big endian order as per DER
    // specification.
    //
    to[putpos++] = getp[i--];

    while (i >= 0) {
        to[putpos++] = getp[i--];
    }

    return putpos;
}

uint32_t MPMath::Encode_Bounded(uint8_t *to, uint32_t tobytes, const mp_digit_u *from, int32_t precision)
{
    DEBUG_ASSERT(to != nullptr);
    DEBUG_ASSERT(from != nullptr);
    DEBUG_ASSERT(tobytes > 0);
    DEBUG_ASSERT(precision > 0);

    mp_digit_u buffer[MAX_UNIT_PRECISION];
    Move_HTOLE(buffer, from, precision);

    uint32_t frombytes = BYTES_PER_UNIT * precision;
    uint8_t sign = (from[precision - 1] & 0x800000000) != 0 ? 0xFF : 0x00;

    for (unsigned i = 0; i < tobytes - frombytes; ++i) {
        *to++ = sign;
    }

    uint32_t copybytes = frombytes > tobytes ? tobytes : frombytes;

    const uint8_t *getp = copybytes + reinterpret_cast<const uint8_t *>(buffer);

    for (unsigned i = 0; i < copybytes; ++i) {
        *to++ = *--getp;
    }

    return tobytes;
}

int32_t MPMath::DER_Encode(const mp_digit_u *from, uint8_t *output, int32_t precision)
{
    DEBUG_ASSERT(from != nullptr);
    DEBUG_ASSERT(output != nullptr);
    DEBUG_ASSERT(precision > 0);

    // Sufficient buffer for max length integer plus meta data.
    uint8_t buffer[MAX_BYTE_PRECISION + 44];

    // Encode our large int to our buffer
    int32_t datalen = Encode(buffer, from, precision);

    // 2 is a flag in the DER encoding scheme indication it contains an integer
    *output = 2;

    // Encode meta data about our integer, essentially its length
    int32_t metalen = DER_Length_Encode(datalen, output + 1) + 1;

    // Copy the encoded data from the buffer to destination
    memcpy((metalen + output), buffer, datalen);

    return datalen + metalen;
}

void MPMath::Signed_Decode(mp_digit_u *result, uint8_t const *from, int32_t frombytes, int32_t precision)
{
    DEBUG_ASSERT(result != nullptr);
    DEBUG_ASSERT(from != nullptr);
    DEBUG_ASSERT(frombytes > 0);
    DEBUG_ASSERT(precision > 0);

    mp_digit_u buffer[MAX_UNIT_PRECISION];

    uint8_t sign = from[0] & 0x80 ? 0xFF : 0x00;
    uint8_t *resp = reinterpret_cast<uint8_t *>(buffer);

    int i;

    for (i = precision * BYTES_PER_UNIT; i > frombytes; --i) {
        *(resp + i - 1) = sign;
    }

    for (; i > 0; --i) {
        *(resp + i - 1) = *(from + frombytes - i);
    }

    Move_LETOH(result, buffer, precision);
}

void MPMath::Unsigned_Decode(mp_digit_u *result, uint8_t const *from, int32_t frombytes, int32_t precision)
{
    DEBUG_ASSERT(result != nullptr);
    DEBUG_ASSERT(from != nullptr);
    DEBUG_ASSERT(frombytes > 0);
    DEBUG_ASSERT(precision > 0);

    mp_digit_u buffer[MAX_UNIT_PRECISION];

    uint8_t *resp = reinterpret_cast<uint8_t *>(buffer);

    int i;

    for (i = precision * BYTES_PER_UNIT; i > frombytes; --i) {
        *(resp + i - 1) = 0;
    }

    for (; i > 0; --i) {
        *(resp + i - 1) = *(from + frombytes - i);
    }

    Move_LETOH(result, buffer, precision);
}

void MPMath::DER_Decode(mp_digit_u *result, uint8_t const *input, int32_t precision)
{
    DEBUG_ASSERT(result != nullptr);
    DEBUG_ASSERT(input != nullptr);
    DEBUG_ASSERT(precision > 0);

    uint32_t numlen;

    // DER encoding identifies encoded integers with a leading 0x02 byte.
    if (*input != 2) {
        return;
    }

    input++;

    // Decode the length of the encoded integer
    if (*input & 0x80) {
        int tmp = *input++ & 127;

        if (tmp > 2) {
            return;
        }

        numlen = *input++;

        if (tmp > 1) {
            numlen = *input++ | (numlen << 8);
        }
    } else {
        numlen = *input++;
    }

    // Decode the integer data
    if (numlen <= (BYTES_PER_UNIT * precision)) {
        Signed_Decode(result, input, numlen, precision);
    }
}

void MPMath::Not(mp_digit_u *number, int32_t precision)
{
    DEBUG_ASSERT(number != nullptr);
    DEBUG_ASSERT(precision > 0);

    for (int i = 0; i < precision; ++i) {
        number[i] = ~number[i];
    }
}

void MPMath::Inc(mp_digit_u *number, int32_t precision)
{
    DEBUG_ASSERT(number != nullptr);
    DEBUG_ASSERT(precision > 0);

    // Loop through and increment each unit of the number.
    for (int i = 0; i < precision; ++i) {
        ++number[i];

        // If its not 0 then it hasn't rolled over so we don't need to increment
        // the next one.
        if (number[i] != 0) {
            break;
        }
    }
}

void MPMath::Dec(mp_digit_u *number, int32_t precision)
{
    DEBUG_ASSERT(number != nullptr);
    DEBUG_ASSERT(precision > 0);

    // Loop through and decrement each unit of the number.
    for (int i = 0; i < precision; ++i) {
        --number[i];

        // If we haven't rolled under we don't need to decrement the next unit.
        if (number[i] != MAX_XMPU) {
            break;
        }
    }
}

void MPMath::Neg(mp_digit_u *number, int32_t precision)
{
    DEBUG_ASSERT(number != nullptr);
    DEBUG_ASSERT(precision > 0);

    Not(number, precision);
    Inc(number, precision);
}

void MPMath::Abs(mp_digit_u *number, int32_t precision)
{
    DEBUG_ASSERT(number != nullptr);
    DEBUG_ASSERT(precision > 0);

    // Check if the last unsigned would be negative if taken as a signed int and
    // negate if so to get +ve version.
    if ((number[precision - 1] & SIGN_BIT) != 0) {
        Neg(number, precision);
    }
}

void MPMath::Shift_Right_Bits(mp_digit_u *number, uint32_t bits, int32_t precision)
{
    DEBUG_ASSERT(number != nullptr);
    DEBUG_ASSERT(bits >= 0);
    DEBUG_ASSERT(precision > 0);
    ;

    // Shift 0 bytes right, we are already done.
    if (bits == 0) {
        return;
    }

    // If bits is the same as the size of the units, just shuffle units right.
    if (bits == DIGITSIZE) {
        for (int i = 0; i < precision - 1; ++i) {
            number[i] = number[i + 1];
        }

        number[precision - 1] = 0;
    } else {
        if (bits > (DIGITSIZE - 1)) { // Shift greater than DIGITSIZE

            int32_t units = bits / DIGITSIZE;
            int32_t remainder = bits % DIGITSIZE;

            int i;

            for (i = 0; i < precision - 1 - units; ++i) {
                number[i] = (number[i + units + 1] << (DIGITSIZE - remainder)) | (number[i + units] >> remainder);
            }

            if (units < precision) {
                number[i] = number[i + units] >> remainder;
                ++i;
            }

            for (; i < precision; ++i) {
                number[i] = 0;
            }
        } else { // Shift less than DIGITSIZE
            uint32_t tmp1 = 0;
            uint32_t tmp2 = 0;

            for (int i = precision - 1; i >= 0; --i) {
                tmp2 = number[i];
                number[i] = (number[i] >> bits) | (tmp1 << (DIGITSIZE - bits));
                tmp1 = ((1 << bits) - 1) & tmp2;
            }
        }
    }
}

void MPMath::Shift_Left_Bits(mp_digit_u *number, uint32_t bits, int32_t precision)
{
    DEBUG_ASSERT(number != nullptr);
    DEBUG_ASSERT(bits >= 0);
    DEBUG_ASSERT(precision > 0);

    // Our work is already done.
    if (bits == 0) {
        return;
    }

    // If bits is the same as the size of the units, just shuffle units left.
    if (bits == DIGITSIZE) {
        for (int i = precision - 1; i > 0; --i) {
            number[i] = number[i - 1];
        }

        number[0] = 0;
    } else {
        if (bits > (DIGITSIZE - 1)) { // shift greater than DIGITSIZE

            int32_t units = bits / DIGITSIZE;
            int32_t remainder = bits % DIGITSIZE;

            // handle big chunks first
            int i;
            for (i = precision - 1; i > units; --i) {
                number[i] = (number[i - units - 1] >> (DIGITSIZE - remainder)) | (number[i - units] << remainder);
            }

            // then remainder
            if (units < precision) {
                number[i] = number[i - units] << remainder;
                i--;
            }

            // then pad 0's
            for (; i >= 0; --i) {
                number[i] = 0;
            }

        } else { // Shift less than DIGITSIZE
            for (unsigned i = precision - 1; i > 0; --i) {
                number[i] = (number[i - 1] >> (DIGITSIZE - bits)) | number[i] << bits;
            }

            number[0] <<= bits;
        }
    }
}

mp_digit_u MPMath::Rotate_Left(mp_digit_u *number, mp_digit_u carry, int32_t precision)
{
    DEBUG_ASSERT(number != nullptr);
    DEBUG_ASSERT(precision > 0);

    for (int i = 0; i < precision; ++i) {
        mp_digit_u nextcarry = number[i] & 0x800000000 ? true : false;

        number[i] = number[i] << 1;

        if (carry) {
            number[i]++;
        }

        carry = nextcarry;
    }

    return carry;
}

mp_digit_u MPMath::Rotate_Right(mp_digit_u *number, mp_digit_u carry, int32_t precision)
{
    DEBUG_ASSERT(number != nullptr);
    DEBUG_ASSERT(precision > 0);

    for (int i = precision - 1; i >= 0; --i) {
        mp_digit_u nextcarry = number[i] & 0x000000001 ? true : false;

        number[i] = number[i] >> 1;

        if (carry) {
            number[i] &= 0x80000000;
        }

        carry = nextcarry;
    }

    return carry;
}

BOOL MPMath::Test_Eq_Int(const mp_digit_u *number, int32_t i, int32_t precision)
{
    DEBUG_ASSERT(number != nullptr);
    DEBUG_ASSERT(precision > 0);

    //
    // If we only have one significant unit and it matches our i, then we
    // are equal.
    //
    if (*number == (uint32_t)i && Significance(number, precision) <= 1) {
        return true;
    }

    return false;
}

int MPMath::Compare(const mp_digit_u *left_number, const mp_digit_u *right_number, int32_t precision)
{
    DEBUG_ASSERT(left_number != nullptr);
    DEBUG_ASSERT(right_number != nullptr);
    DEBUG_ASSERT(precision > 0);

    // Start with most significant figure and work backwards.
    for (int i = precision - 1; i >= 0; --i) {
        // left_number is less than right_number, -1 indicates less than.
        if (left_number[i] < right_number[i]) {
            return -1;
        }

        // left_number is greater than num 2, +1 indicates greater than.
        if (left_number[i] > right_number[i]) {
            return 1;
        }
    }

    // Both numbers are equal if we reach here.
    return 0;
}

mp_digit_u MPMath::Add(
    mp_digit_u *result, const mp_digit_u *left_number, const mp_digit_u *right_number, mp_digit_u carry, int32_t precision)
{
    DEBUG_ASSERT(result != nullptr);
    DEBUG_ASSERT(left_number != nullptr);
    DEBUG_ASSERT(right_number != nullptr);
    DEBUG_ASSERT(precision > 0);

    for (int i = 0; i < precision; ++i) {
        mp_digit_u nextcarry = Add_Carry(left_number[i], right_number[i], carry);
        result[i] = right_number[i] + left_number[i] + carry;
        carry = nextcarry;
    }

    return carry;
}

mp_digit_u MPMath::Add_Int(
    mp_digit_u *result, const mp_digit_u *left_number, mp_digit_u right_number, mp_digit_u carry, int32_t precision)
{
    DEBUG_ASSERT(result != nullptr);
    DEBUG_ASSERT(left_number != nullptr);
    DEBUG_ASSERT(right_number != 0);
    DEBUG_ASSERT(precision > 0);

    for (int i = 0; i < precision; ++i) {
        mp_digit_u nextcarry = Add_Carry(left_number[i], right_number, carry);
        result[i] = left_number[i] + right_number + carry;
        right_number = 0;
        carry = nextcarry;
    }

    return carry;
}

mp_digit_u MPMath::Sub(
    mp_digit_u *result, const mp_digit_u *left_number, const mp_digit_u *right_number, mp_digit_u borrow, int32_t precision)
{
    DEBUG_ASSERT(result != nullptr);
    DEBUG_ASSERT(left_number != nullptr);
    DEBUG_ASSERT(right_number != nullptr);
    DEBUG_ASSERT(precision > 0);

    for (int i = 0; i < precision; i++) {
        mp_digit_u nextborrow = Sub_Carry(left_number[i], right_number[i], borrow);
        result[i] = left_number[i] - right_number[i] - borrow;
        borrow = nextborrow;
    }

    return borrow;
}

mp_digit_u MPMath::Sub_Int(
    mp_digit_u *result, const mp_digit_u *left_number, mp_digit_u right_number, mp_digit_u borrow, int32_t precision)
{
    DEBUG_ASSERT(result != nullptr);
    DEBUG_ASSERT(left_number != nullptr);
    DEBUG_ASSERT(right_number != 0);
    DEBUG_ASSERT(precision > 0);

    for (int i = 0; i < precision; i++) {
        mp_digit_u nextborrow = Sub_Carry(left_number[i], right_number, borrow);
        result[i] = left_number[i] - right_number - borrow;
        right_number = 0;
        borrow = nextborrow;
    }

    return borrow;
}

int32_t MPMath::Unsigned_Mul(mp_digit_u *prod, const mp_digit_u *multiplicand, const mp_digit_u *multiplier, int32_t precision)
{
    DEBUG_ASSERT(prod != nullptr);
    DEBUG_ASSERT(multiplicand != nullptr);
    DEBUG_ASSERT(multiplier != nullptr);
    DEBUG_ASSERT(precision > 0);

    Init(prod, 0, precision);

    // Test for trivial case of multiply by 0 and return
    if (Test_Eq_Int(multiplicand, 0, precision) != 0 || Test_Eq_Int(multiplier, 0, precision) != 0) {
        return 0;
    }

    int32_t num2_bits = Count_Bits(multiplier, precision);
    uint32_t high_bit_mask = num2_bits != 0 ? 1 << ((num2_bits - 1) % 32) : 0;
    int32_t units = Bits_To_Units(num2_bits);

    // Multiple using serial addition for each tested bit in multiplier.
    if (units != 0) {
        const mp_digit_u *num2_ptr = &multiplier[units - 1];

        for (int i = num2_bits - 1; i >= 0; --i) {
            Shift_Left_Bits(prod, 1, precision);

            if ((*num2_ptr & high_bit_mask) != 0) {
                Add(prod, prod, multiplicand, 0, precision);
            }

            high_bit_mask >>= 1;

            if (high_bit_mask == 0) {
                high_bit_mask = 0x80000000;
                --num2_ptr;
            }
        }
    }

    return 0;
}

int32_t MPMath::Unsigned_Mul_Int(mp_digit_u *prod, const mp_digit_u *multiplicand, mp_digit_s multiplier, int32_t precision)
{
    DEBUG_ASSERT(prod != nullptr);
    DEBUG_ASSERT(multiplicand != nullptr);
    DEBUG_ASSERT(multiplier != 0);
    DEBUG_ASSERT(precision > 0);

    // Test for trivial case of multiply by 0 and return
    if (Test_Eq_Int(multiplicand, 0, precision) != 0 || multiplier == 0) {
        return 0;
    }

    // Using double sized unit to hold results in order to capture remainder.
    // Original code treated array as 16bit ints to use a 32bit int to hold the
    // remainder, but that is only needed on machines with no 64bit type which
    // we aren't going to care about these days.
    mp_digit_du tmp = 0;

    for (int i = 0; i < precision; ++i) {
        tmp = tmp + (multiplicand[i] * (mp_digit_ds)multiplier);
        prod[i] = tmp;
        tmp >>= 32;
    }

    return 0;
}

int32_t MPMath::Unsigned_Mul_Int16(mp_digit_u *prod, mp_digit_u *multiplicand, int16_t multiplier, int32_t precision)
{
    DEBUG_ASSERT(prod != nullptr);
    DEBUG_ASSERT(multiplicand != nullptr);
    DEBUG_ASSERT(multiplier != 0);
    DEBUG_ASSERT(precision > 0);

    // Test for trivial case of multiply by 0 and return
    if (Test_Eq_Int(multiplicand, 0, precision) != 0 || multiplier == 0) {
        return 0;
    }

    // This is how the original code worked. Only really useful for comparing to
    // the new code as its not as endian friendly (assumes little endian) and
    // has twice as many operations, but should give the same result.
    mp_digit_u tmp = 0;
    uint16_t *numptr = reinterpret_cast<uint16_t *>(multiplicand);
    uint16_t *resptr = reinterpret_cast<uint16_t *>(prod);

    for (int i = 0; i < precision * 2; ++i) {
        tmp = tmp + (numptr[i] * (mp_digit_s)multiplier);
        resptr[i] = tmp;
        tmp >>= 16;
    }

    return 0;
}

int32_t MPMath::Signed_Mul(mp_digit_u *prod, const mp_digit_u *multiplicand, const mp_digit_u *multiplier, int32_t precision)
{
    DEBUG_ASSERT(prod != nullptr);
    DEBUG_ASSERT(multiplicand != nullptr);
    DEBUG_ASSERT(multiplier != nullptr);
    DEBUG_ASSERT(precision > 0);

    mp_digit_u abs_multiplier[MAX_UNIT_PRECISION];
    mp_digit_u abs_multiplicand[MAX_UNIT_PRECISION];

    if ((multiplicand[precision - 1] & SIGN_BIT) == 0) {
        if ((multiplier[precision - 1] & SIGN_BIT) == 0) {
            Unsigned_Mul(prod, multiplicand, multiplier, precision);

            return 0;
        }

        Move(abs_multiplier, multiplier, precision);
        Neg(abs_multiplier, precision);

        Unsigned_Mul(prod, multiplicand, abs_multiplier, precision);
        Neg(prod, precision);

        return 0;
    }

    Move(abs_multiplicand, multiplicand, precision);
    Neg(abs_multiplicand, precision);

    if ((multiplier[precision - 1] & SIGN_BIT) == 0) {
        Unsigned_Mul(prod, abs_multiplicand, multiplier, precision);
        Neg(prod, precision);

        return 0;
    }

    Move(abs_multiplier, multiplier, precision);
    Neg(abs_multiplier, precision);
    Unsigned_Mul(prod, abs_multiplicand, abs_multiplier, precision);

    return 0;
}

int32_t MPMath::Signed_Mul_Int(mp_digit_u *prod, mp_digit_u *multiplicand, mp_digit_u multiplier, int32_t precision)
{
    DEBUG_ASSERT(prod != nullptr);
    DEBUG_ASSERT(multiplicand != nullptr);
    DEBUG_ASSERT(multiplier != 0);
    DEBUG_ASSERT(precision > 0);

    mp_digit_u abs_multiplicand[MAX_UNIT_PRECISION];

    if ((multiplicand[precision - 1] & SIGN_BIT) == 0) {
        Move(abs_multiplicand, multiplicand, precision);
        Neg(abs_multiplicand, precision);

        if ((mp_digit_s)multiplier < 0) {
            multiplier = -(mp_digit_s)multiplier;
            Unsigned_Mul_Int(prod, abs_multiplicand, multiplier, precision);

            return 0;
        }

        Unsigned_Mul_Int(prod, abs_multiplicand, multiplier, precision);
        Neg(prod, precision);

        return 0;
    }

    if ((mp_digit_s)multiplier >= 0) {
        Unsigned_Mul_Int(prod, multiplicand, multiplier, precision);

        return 0;
    }

    multiplier = -(mp_digit_s)multiplier;
    Unsigned_Mul_Int(prod, multiplicand, multiplier, precision);
    Neg(prod, precision);

    return 0;
}

void MPMath::Hybrid_Mul(mp_digit_u *prod, mp_digit_u *multiplicand, mp_digit_u multiplier, int32_t precision)
{
    mp_digit_du carry = 0;

    for (int i = 0; i < precision; ++i) {
        mp_digit_du mult = (mp_digit_du)multiplicand[i] * (mp_digit_du)multiplier;
        carry = mult + carry + *prod;
        *prod = carry;
        ++prod;
        carry >>= DIGITSIZE;
    }

    prod += carry;
}

void MPMath::Double_Mul(mp_digit_u *prod, mp_digit_u *multiplicand, mp_digit_u *multiplier, int32_t precision)
{
    Init(prod, 0, 2 * precision);

    for (int i = 0; i < precision; ++i) {
        Hybrid_Mul(&prod[i], multiplicand, multiplier[i], precision);
    }
}

int32_t MPMath::Unsigned_Div(
    mp_digit_u *remainder, mp_digit_u *quotient, const mp_digit_u *dividend, const mp_digit_u *divisor, int32_t precision)
{
    DEBUG_ASSERT(remainder != nullptr);
    DEBUG_ASSERT(quotient != nullptr);
    DEBUG_ASSERT(dividend != nullptr);
    DEBUG_ASSERT(divisor != nullptr);
    DEBUG_ASSERT(precision > 0);

    // total_bit_count

    // Divide by zero error!
    if (Test_Eq_Int(divisor, 0, precision) != 0) {
        return -1;
    }

    Init(remainder, 0, precision);
    Init(quotient, 0, precision);

    int32_t num1_bits = Count_Bits(dividend, precision);
    int32_t units = Bits_To_Units(num1_bits);

    if (units != 0) {
        const mp_digit_u *num1ptr = &dividend[units - 1];
        mp_digit_u *resptr = &quotient[units - 1];
        uint32_t high_bit_mask = num1_bits != 0 ? 1 << ((num1_bits - 1) % 32) : 0;

        // Divide by serial subtraction?
        for (int i = num1_bits - 1; i >= 0; --i) {
            Shift_Left_Bits(remainder, 1, precision);

            if ((*num1ptr & high_bit_mask) != 0) {
                Inc(remainder, precision);
            }

            if (Compare(remainder, divisor, precision) >= 0) {
                Sub(remainder, remainder, divisor, 0, precision);
                *resptr |= high_bit_mask;
            }

            high_bit_mask >>= 1;

            if (high_bit_mask == 0) {
                high_bit_mask = SIGN_BIT;
                --num1ptr;
                --resptr;
            }
        }
    }

    return 0;
}

uint32_t MPMath::Unsigned_Div_Int(mp_digit_u *quotient, const mp_digit_u *dividend, mp_digit_u divisor, int32_t precision)
{
    DEBUG_ASSERT(quotient != nullptr);
    DEBUG_ASSERT(dividend != nullptr);
    DEBUG_ASSERT(divisor > 0);
    DEBUG_ASSERT(precision > 0);

    // Divide by zero error!
    if (divisor == 0) {
        return 0;
    }

    Init(quotient, 0, precision);

    int32_t num1_bits = Count_Bits(dividend, precision);
    int32_t units = Bits_To_Units(num1_bits);
    uint32_t remain = 0;

    if (units != 0) {
        const mp_digit_u *num1ptr = &dividend[units - 1];
        mp_digit_u *resptr = &quotient[units - 1];
        uint32_t high_bit_mask = num1_bits != 0 ? 1 << ((num1_bits - 1) % 32) : 0;

        // Divide by serial subtraction?
        for (int i = num1_bits - 1; i >= 0; --i) {
            remain <<= 1;

            if ((*num1ptr & high_bit_mask) != 0) {
                ++remain;
            }

            if (remain >= divisor) {
                remain -= divisor;
                *resptr |= high_bit_mask;
            }

            high_bit_mask >>= 1;

            if (high_bit_mask == 0) {
                high_bit_mask = SIGN_BIT;
                --num1ptr;
                --resptr;
            }
        }
    }

    return remain;
}

void MPMath::Signed_Div(
    mp_digit_u *remainder, mp_digit_u *quotient, mp_digit_u *dividend, mp_digit_u *divisor, int32_t precision)
{
    DEBUG_ASSERT(remainder != nullptr);
    DEBUG_ASSERT(quotient != nullptr);
    DEBUG_ASSERT(dividend != nullptr);
    DEBUG_ASSERT(divisor != nullptr);
    DEBUG_ASSERT(precision > 0);

    mp_digit_u scratch_divisor[MAX_UNIT_PRECISION];
    mp_digit_u scratch_dividend[MAX_UNIT_PRECISION];

    Move(scratch_dividend, dividend, precision);
    Move(scratch_divisor, divisor, precision);

    mp_digit_u invert = false;

    if ((scratch_dividend[precision - 1] & SIGN_BIT) == 0) {
        Neg(scratch_dividend, precision);
        invert = true;
    }

    if ((scratch_divisor[precision - 1] & SIGN_BIT) == 0) {
        Neg(scratch_divisor, precision);
        // invert = !invert;
        invert = (invert == false);
    }

    // If both were positive or both were negative and were inverted, we only
    // need to do unsigned division on them.
    Unsigned_Div(remainder, quotient, scratch_dividend, scratch_divisor, precision);

    // If only one is negative, then we need to do some more maths.
    if (invert) {
        Neg(quotient, precision);

        if (Test_Eq_Int(remainder, 0, precision) == 0) {
            Dec(quotient, precision);
            Neg(remainder, precision);
            Add(remainder, remainder, scratch_divisor, 0, precision);
        }
    }
}

void MPMath::Modulo(mp_digit_u *remainder, mp_digit_u *num1, mp_digit_u *num2, int32_t precision)
{
    DEBUG_ASSERT(remainder != nullptr);
    DEBUG_ASSERT(num1 != nullptr);
    DEBUG_ASSERT(num2 != nullptr);
    DEBUG_ASSERT(precision > 0);

    // Divide by zero error!
    if (Test_Eq_Int(num2, 0, precision) != 0) {
        return;
    }

    Init(remainder, 0, precision);

    int32_t num1_bits = Count_Bits(num1, precision);
    int32_t units = Bits_To_Units(num1_bits);

    if (units != 0) {
        mp_digit_u *num1ptr = &num1[units - 1];
        uint32_t high_bit_mask = num1_bits != 0 ? 1 << ((num1_bits - 1) % 32) : 0;

        // Divide by serial subtraction?
        for (int i = num1_bits - 1; i >= 0; --i) {
            Shift_Left_Bits(remainder, 1, precision);

            if ((*num1ptr & high_bit_mask) != 0) {
                Inc(remainder, precision);
            }

            if (Compare(remainder, num2, precision) >= 0) {
                Sub(remainder, remainder, num2, 0, precision);
            }

            high_bit_mask >>= 1;

            if (high_bit_mask == 0) {
                high_bit_mask = SIGN_BIT;
                --num1ptr;
            }
        }
    }
}

void MPMath::Inverse_A_Mod_B(mp_digit_u *result, const mp_digit_u *number, const mp_digit_u *modulus, int32_t precision)
{
    DEBUG_ASSERT(result != nullptr);
    DEBUG_ASSERT(number != nullptr);
    DEBUG_ASSERT(modulus != nullptr);
    DEBUG_ASSERT(precision > 0);

    mp_digit_u y[MAX_UNIT_PRECISION];
    mp_digit_u g[3][MAX_UNIT_PRECISION];
    mp_digit_u v[3][MAX_UNIT_PRECISION];

    Move(g[0], modulus, precision);
    Move(g[1], number, precision);

    Init(v[0], 0, precision);
    Init(v[1], 1, precision);

    // This loops until g[i%3] is 0 cycling between 3 number buffers to
    // carry the results of the previous loop to the next.
    unsigned i;
    for (i = 1; Test_Eq_Int(g[i % 3], 0, precision) != 0; ++i) {
        unsigned imod = i % 3;
        unsigned idec = (i - 1) % 3;
        unsigned iinc = (i + 1) % 3;

        Unsigned_Div(g[iinc], y, g[idec], g[imod], precision);
        Unsigned_Mul(result, v[imod], y, precision);
        Sub(v[iinc], v[idec], result, false, precision);
    }

    // The result is in v[(i - 1) % 3], if its negative add modulus to it.
    unsigned idec = (i - 1) % 3;

    if ((v[idec][precision - 1] & SIGN_BIT) != 0) {
        Add(v[idec], v[idec], modulus, 0, precision);
    }

    Move(result, v[idec], precision);
}

int32_t MPMath::Reciprocal(mp_digit_u *quotient, const mp_digit_u *divisor, int32_t precision)
{
    DEBUG_ASSERT(quotient != nullptr);
    DEBUG_ASSERT(divisor != nullptr);
    DEBUG_ASSERT(precision > 0);

    mp_digit_u remainder[MAX_UNIT_PRECISION];

    // Divide by zero error?
    if (Test_Eq_Int(divisor, 0, precision)) {
        return -1;
    }

    Init(quotient, 0, precision);
    Init(remainder, 0, precision);

    int32_t bits = Count_Bits(divisor, precision);
    uint32_t high_bit_mask = Unit_Sig_Bit(bits + 1);
    Set_Bit(remainder, bits - 1);
    mp_digit_u *resptr = &quotient[((bits + DIGITSIZE) / DIGITSIZE) - 1];

    for (int i = bits - 1; i >= 0; --i) {
        Shift_Left_Bits(remainder, 1, precision);

        if (Compare(remainder, divisor, precision) != -1) {
            Sub(remainder, remainder, (mp_digit_u *)divisor, 0, precision);
            *resptr |= high_bit_mask;
        }

        high_bit_mask >>= 1;

        if (!high_bit_mask) {
            high_bit_mask = SIGN_BIT;
            --resptr;
        }
    }

    // For security purposes, it clears sensitive data on the stack.
    Init(remainder, 0, precision);

    return 0;
}

int32_t MPMath::Mod_Mul_Upton(mp_digit_u *result, mp_digit_u *num1, mp_digit_u *num2, int32_t precision)
{
    Double_Mul(_double_staging_number, num1, num2, precision);
    Move(_upton_dhi, &_double_staging_number[_upton_bitsdiv], precision);
    Shift_Right_Bits(_upton_dhi, _upton_bitsmod, precision);

    Double_Mul(_upton_e_number, _upton_dhi, _upton_reciprocal, precision);
    Shift_Right_Bits(&_upton_e_number[_upton_bitsdiv], _upton_bitsmod, precision);

    Double_Mul(_upton_f_number, &_upton_e_number[_upton_bitsdiv], _scratch_modulus, precision);
    Sub(_double_staging_number, _double_staging_number, _upton_f_number, 0, precision * 2);

    while (Compare(_double_staging_number, _scratch_modulus, precision) > 0) {
        Sub(_double_staging_number, _double_staging_number, _scratch_modulus, 0, precision);
    }

    Move(result, _double_staging_number, precision);

    return 0;
}

void MPMath::Prepare_Modulus_Upton(const mp_digit_u *modulus, int32_t precision)
{
    Move(_scratch_modulus, modulus, precision);
    Reciprocal(_upton_reciprocal, modulus, precision);
    int bits = Count_Bits(modulus, precision);
    _upton_bitsdiv = bits / DIGITSIZE;
    _upton_bitsmod = bits % DIGITSIZE;
}

void MPMath::Mod_Mult_Clear_Upton(int32_t precision)
{
    Init(_scratch_modulus, 0, MAX_UNIT_PRECISION);
    Init(_upton_reciprocal, 0, MAX_UNIT_PRECISION);
    Init(_upton_dhi, 0, MAX_UNIT_PRECISION);
    Init(_double_staging_number, 0, MAX_UNIT_PRECISION * 2 + 2);
    Init(_upton_e_number, 0, MAX_UNIT_PRECISION * 2 + 2);
    Init(_upton_f_number, 0, MAX_UNIT_PRECISION * 2 + 2);
    _upton_bitsdiv = _upton_bitsmod = 0;
}

int MPMath::Exponent_Mod(
    mp_digit_u *expout, mp_digit_u *expin, const mp_digit_u *exponent_ptr, const mp_digit_u *modulus, int32_t precision)
{
    mp_digit_u product[MAX_UNIT_PRECISION];

    if (Test_Eq_Int(exponent_ptr, 0, precision)) {
        return !Test_Eq_Int(expin, 0, precision) - 1;
    }

    if (Test_Eq_Int(modulus, 0, precision)) {
        return -2;
    }

    if (Compare(expin, modulus, precision) >= 0) {
        return -3;
    }

    if (Compare(exponent_ptr, modulus, precision) >= 0) {
        return -4;
    }

    Init(expout, 1, precision);
    int32_t mod_precision = Significance(modulus, precision);
    Prepare_Modulus_Upton(modulus, precision);

    int32_t bits = Count_Bits(exponent_ptr, mod_precision);
    int32_t units = Bits_To_Units(bits);

    if (units > 0) {
        uint32_t high_bit_mask = Unit_Sig_Bit(bits);
        Move(expout, expin, mod_precision);

        high_bit_mask >>= 1;

        if (high_bit_mask == 0) {
            high_bit_mask = SIGN_BIT;
            --units;
        }

        int round = 0;

        for (int i = units; i > 0;) {
            // Square + Mod
            Mod_Mul_Upton(product, expout, expout, precision);

            if ((exponent_ptr[i - 1] & high_bit_mask) != 0) {
                Mod_Mul_Upton(expout, product, expin, precision);
            } else {
                Move(expout, product, precision);
            }

            high_bit_mask >>= 1;

            if (high_bit_mask == 0) {
                high_bit_mask = SIGN_BIT;
                --i;
            }
            ++round;
        }

        Init(product, 0, precision);
        Mod_Mult_Clear_Upton(precision);
    }

    return 0;
}

uint16_t const *MPMath::Fetch_Prime_Table()
{
    return mp_primeTable;
}

int MPMath::Fetch_Prime_Size()
{
    return MAX_PRIME_TABLE_SIZE;
}

void MPMath::Decode_ASCII(const char *str, unsigned int *mpn, int precision)
{
    // minus
    // COMPILER_TODO("");
}

mp_digit_u MPMath::Rabin_Miller_Test(Straw *rng, const unsigned int *w, int rounds, int precision)
{
    //COMPILER_TODO("");
    return 0;
}

BOOL MPMath::Fermat_Test(const mp_digit_u *candidate_prime, unsigned int rounds, int precision)
{
    mp_digit_u term[MAX_UNIT_PRECISION];
    mp_digit_u small_prime[MAX_UNIT_PRECISION];
    mp_digit_u result[MAX_UNIT_PRECISION];

    Move(term, candidate_prime, precision);
    Dec(term, precision);

    for (unsigned i = 0; i < rounds; ++rounds) {
        Init(small_prime, mp_primeTable[i], precision);
        Exponent_Mod(result, small_prime, term, candidate_prime, precision);

        if (!Test_Eq_Int(result, 1, precision)) {
            return false;
        }
    }

    return true;
}

BOOL MPMath::Is_Small_Prime(const mp_digit_u *candidate, int precision)
{
    if (Significance(candidate, precision) <= 1 && *candidate <= mp_primeTable[MAX_PRIME_TABLE_SIZE - 1]) {
        return bsearch(candidate, mp_primeTable, MAX_PRIME_TABLE_SIZE, sizeof(mp_primeTable[0]), Prime_Compare_Func)
            != nullptr;
    }

    return false;
}

BOOL MPMath::Is_Prime(const mp_digit_u *prime, int precision)
{
    if (*prime & 1) {
        if (Is_Small_Prime(prime, precision)) {
            return true;
        } else {
            if (Small_Divisors_Test(prime, precision)) {
                return Fermat_Test(prime, 2, precision);
            }
        }
    }

    return false;
}

void MPMath::Randomize_Bounded(
    mp_digit_u *result, Straw *rng, const mp_digit_u *minval, const mp_digit_u *maxval, int precision)
{
    unsigned int range[MAX_UNIT_PRECISION];

    Sub(range, maxval, minval, 0, precision);
    int bits = Count_Bits(range, precision);

    do {
        Randomize(result, rng, bits, precision);
    } while (Compare(result, range, precision) > 0);

    Add(result, result, minval, 0, precision);
}

void MPMath::Randomize(mp_digit_u *result, Straw *rng, int total_bits, int precision)
{
    int bits = Min(total_bits, (int)DIGITSIZE * precision);
    Init(result, 0, precision);
    rng->Get(result, bits / 8 + 1);
    reinterpret_cast<uint8_t *>(result)[bits / 8] &= ~(-1 << bits % 8);
}

BOOL MPMath::Small_Divisors_Test(const mp_digit_u *candidate, int precision)
{
    mp_digit_u quotient[MAX_UNIT_PRECISION];

    int i = 0;

    while (Unsigned_Div_Int(quotient, (mp_digit_u *)candidate, mp_primeTable[i], precision)) {
        ++i;

        if (i >= MAX_PRIME_TABLE_SIZE) {
            return true;
        }
    }

    return false;
}
